package jdt.geom;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import com.google.common.collect.Sets;

/**
 * An instance of this class can iteratively build the convex hull for a set
 * points
 * 
 * @author Shay
 * 
 */
public class ConvexHull {

	/** All the points to calculate the convex hull for */
	private Set<Point> allPoints = new HashSet<Point>();

	/** The edges of the convex hull in clockwize order */
	private Set<Edge> convexHullEdges;

	/** The points of the convex hull */
	private Set<Point> convexHullPoints;
	
	/** Should the convex hull be calculated before next get call */
	private boolean dirty;

	/* --- Ctors. --- */

	/**
	 * The default constructor
	 */
	public ConvexHull() {
		convexHullEdges = new HashSet<Edge>();
		convexHullPoints = new HashSet<Point>();
	}

	/**
	 * Construct a convex hull for all the argument points
	 * 
	 * @param points
	 *            A collection of points
	 */
	public ConvexHull(Collection<Point> points) {
		allPoints.addAll(points);
		dirty = true;
	}

	/* --- Public Methods --- */

	/**
	 * Add a point to this convex hull
	 * 
	 * @param p
	 *            The point to add
	 */
	public void addPoint(Point p) {
		allPoints.add(p);
		dirty = true;
	}

	/**
	 * Get all the points in the convex hull
	 * 
	 * @return the points of the convex hull
	 */
	public synchronized Set<Point> getConvexHullPoints() {
		if(dirty){
			calculateConvexHull();
		}
		return this.convexHullPoints;
	}
	
	/**
	 * Get all the edges of the convex hull
	 * 
	 * @return the points of the convex hull
	 */
	public synchronized Set<Edge> getConvexHullEdges() {
		if(dirty){
			calculateConvexHull();
		}
		return this.convexHullEdges;
	}
	
	/**
	 * Gets the edges of this convex hull which will be deleted if the argument
	 * point was inserted to this
	 * 
	 * @param p The point to check
	 * @return set of edges, as described
	 */
	public synchronized Set<Edge> toBeRemovedUponInsertion(Point p){
		if(dirty){
			calculateConvexHull();
		}
		
		if(allPoints.size() < 2){
			return new HashSet<Edge>();
		} else if(allPoints.size() == 2){
			return convexHullEdges;
		} else {
			ConvexHull newHull = new ConvexHull(allPoints);
			newHull.addPoint(p);
			return new HashSet<Edge>(Sets.difference(getConvexHullEdges(), newHull.getConvexHullEdges()));
		}
	}
	
	/* --- Private Methods --- */

	/**
	 * calculate the convex hull
	 */
	private void calculateConvexHull() {
		List<Point> tempPoints = new ArrayList<Point>(allPoints);

		if (tempPoints.size() < 3) {
			convexHullPoints = new HashSet<Point>(tempPoints);
			convexHullEdges = new HashSet<Edge>();
			initAtMostTwoPointsEdges(tempPoints);
			
		} else {
			convexHullEdges = new HashSet<Edge>();
			convexHullPoints = new HashSet<Point>();

			// Find minimum and maximum X points
			Point minXPoint = tempPoints.get(0);
			Point maxXPoint = tempPoints.get(0);
			for (int i = 1; i < tempPoints.size(); i++) {
				if (tempPoints.get(i).getX() > maxXPoint.getX()) {
					maxXPoint = tempPoints.get(i);
				}
				if (tempPoints.get(i).getX() < minXPoint.getX()) {
					minXPoint = tempPoints.get(i);
				}
			}

			// Start calculating the convex hull

			convexHullPoints.add(minXPoint);
			convexHullPoints.add(maxXPoint);

			tempPoints.remove(minXPoint);
			tempPoints.remove(maxXPoint);

			DirectedEdge edgeOnConvexHull = null;
			try {
				edgeOnConvexHull = new DirectedEdge(minXPoint, maxXPoint);
				convexHullEdges.add(edgeOnConvexHull.unDirect());
			} catch (GeometryException e) {
				// can't happen
			}

			// Initialize the left and right sets
			Set<Point> leftSet = getLeftPoints(edgeOnConvexHull, tempPoints);
			Set<Point> rightSet = getRightPoints(edgeOnConvexHull, tempPoints);

			// Recursive call
			try {
				if(rightSet.size() != 0 && leftSet.size() != 0){
					// The edge is not on the convex hull
					convexHullEdges.remove(edgeOnConvexHull.unDirect());
				}
				hullSetAbove(new DirectedEdge(minXPoint, maxXPoint), rightSet, false);
				hullSetAbove(new DirectedEdge(maxXPoint, minXPoint), leftSet, false);
			} catch (GeometryException e) {
				// can't happen
			}
		}

		dirty = false;
		allPoints.retainAll(convexHullPoints);
	}

	private void hullSetAbove(DirectedEdge e, Set<Point> points, boolean remove) {
		if (points.size() == 0) {
			return;
		} else {
			if(remove){
				//e is not an edge of the convex hull
				convexHullEdges.remove(e.unDirect());
			}
			
			// Find the farthest point and create triangles
			Point farthsetPoint = findFarthestPoint(e, points);
			points.remove(farthsetPoint);
			Triangle extendedTriangle = new Triangle(e, farthsetPoint);
			convexHullPoints.add(farthsetPoint);

			// Delete all the points inside the triangles
			for (Iterator<Point> pointsIterator = points.iterator(); 
													pointsIterator.hasNext();) {
				Point p = (Point) pointsIterator.next();
				if (extendedTriangle.contains(p)) {
					pointsIterator.remove();
				}

			}
			
			// Recursive calls
			try {
				DirectedEdge minToNew = new DirectedEdge(e.getPoints().get(0), farthsetPoint);
				handleNewEdge(minToNew, points);
				
				DirectedEdge newToMax = new DirectedEdge(farthsetPoint, e.getPoints().get(1));
				handleNewEdge(newToMax, points);
			} catch (GeometryException ge){
				// can't happen
			}
		}
	}

	private void initAtMostTwoPointsEdges(List<Point> tempPoints) {
		try {
			if(tempPoints.size() == 2){
				convexHullEdges.add(new Edge(tempPoints.get(0), tempPoints.get(1)));
			} 
		} catch (GeometryException e){
			// can't happen
		}
	}
	
	private void handleNewEdge(DirectedEdge e, Set<Point> points){
		Set<Point> aboveTheEdge = getRightPoints(e, points);
		convexHullEdges.add(e.unDirect());
		hullSetAbove(e, aboveTheEdge, true);
	}

	/**
	 * Find the point in the argument points set which is the farthest from
	 * the argument edge
	 * @param e The edge
	 * @param points The points
	 * @return the farthest edge
	 */
	private Point findFarthestPoint(Edge e, Set<Point> points) {
		Point farthestPoint = null;
		double maxDistance = -1;
		for (Point point : points) {
			double distance = e.distance(point);
			if(distance > maxDistance){
				maxDistance = distance;
				farthestPoint = point;
			}
		}
		return farthestPoint;
	}

	/**
	 * Get all the points for the argument point set which are for the right of
	 * the argument edge
	 * 
	 * @param e
	 *            The edge to check
	 * @param points
	 *            The points to check
	 * @return a set of points, as described
	 */
	private Set<Point> getRightPoints(DirectedEdge e, Collection<Point> points) {
		Set<Point> rightPoints = new HashSet<Point>();
		for (Point point : points) {
			if (e.isRightOf(point)) {
				rightPoints.add(point);
			}
		}
		return rightPoints;
	}

	/**
	 * Get all the points for the argument point set which are for the left of
	 * the argument edge
	 * 
	 * @param e
	 *            The edge to check
	 * @param points
	 *            The points to check
	 * @return a set of points, as described
	 */
	private Set<Point> getLeftPoints(DirectedEdge e, Collection<Point> points) {
		Set<Point> rightPoints = getRightPoints(e, points);
		Set<Point> leftPoints = new HashSet<Point>(points);
		leftPoints.removeAll(rightPoints);
		return leftPoints;
	}
}
